package main

import "fmt"

// 如何进行堆排序

func main() {
	array := []int{5, 4, 9, 8, 7, 6, 0, 1, 3, 2}
	minHeapSort(array)
	fmt.Println(array)
}

func minHeapSort(array []int) {
	l := len(array)
	// 对初始树进行排序
	for i := l/2 - 1; i >= 0; i-- {
		adjustMinHeap(array, i, l-1)
	}

	// 从后往前放置当前的树根
	for i := l - 1; i >= 0; i-- {
		temp := array[0]
		array[0] = array[i]
		array[i] = temp
		adjustMinHeap(array, 0, i-1)
	}
}

// pos 指当前节点，l 指终止节点
func adjustMinHeap(a []int, pos, l int) {
	var temp int
	child := 0

	for temp = a[pos]; pos*2+1 <= l; pos = child {
		// 找到左孩子
		child = 2*pos + 1

		// 比较左孩子和右孩子，选择大的
		if child < l && a[child] < a[child+1] {
			child++
		}

		// 若孩子节点更大，则将父节点与孩子节点进行更换
		if a[child] > temp {
			a[pos] = a[child]
		} else {
			break
		}
	}

	a[pos] = temp
}
